#include <stdio.h>
#include <stdlib.h>

#define NIL -1 /* 假设数据为非负整数，NIL定义为非法数据，表示空 */
#define kMaxSize 1000 /* 树结点最大个数 */
#define kMaxStringSize 4 /* 键值最大位数 */
typedef enum {false, true} bool;

/* 树的定义与操作 */
typedef int TElemSet;
typedef struct BinaryTreeNode *BinaryTree;
typedef struct BinaryTreeNode *Position;
struct BinaryTreeNode {
    TElemSet data; /* 数据元素 */
    BinaryTree left; /* 左孩子指针 */
    BinaryTree right; /* 右孩子指针 */
};

int k; /* 当前待处理的元素在preorder中的下标，初始化为-1 */
BinaryTree PreOrderDeSerialize(TElemSet preorder[], int n);
BinaryTree BuildTree();
/* 树的定义与操作结束 */

/* 不相交集的定义与操作 */
typedef int SElemSet; /* 默认元素用非负整数表示 */
typedef SElemSet
SetName; /* 默认用根结点的下标作为集合名称 */
typedef struct SetNode {
    SElemSet parent; /* 父结点 */
    int rank; /* 秩 */
} Set[kMaxSize + 1]; /* 假设集合元素下标从1开始 */

void InitSet(Set set, int n);
SetName Find(Set set, SElemSet x);
void Union(Set set, SElemSet x, SElemSet y);
/* 不相交集的定义与操作结束 */

/* 查询结点对的存储结构 */
typedef int Node; /* 结点为从1开始的正整数 */
typedef struct PairNode *Pair;
struct PairNode {
    Node u, v; /* 待查询的一对结点(u,v) */
    Node lca; /* 记录LCA(u,v) */
};
typedef struct QueryNode *Query;
struct QueryNode {
    Pair nodes; /* 待查询的结点对数组 */
    int size; /* 查询数量，即数组长度 */
};

/* 算法9-7：Tarjan算法求解最近公共祖先 LCA(P, u, set, ancestor, visited) */
void LCA(Query P, Position u, Set set, Node ancestor[], bool visited[]) {
    Position v;
    Node v_data;
    int i;

    if (u == NULL)
        return;
    ancestor[Find(set, u->data)] = u->data; /* 初始化 */
    /* 对u的每个非空的子树 */
    v = u->left;
    if (v != NULL) {
        LCA(P, v, set, ancestor, visited); /* 深度优先遍历 */
        Union(set, u->data, v->data); /* 将子树并到根结点u */
        ancestor[Find(set, u->data)] = u->data; /* 记录这棵树的根是u */
    }
    v = u->right; /* 右子树同上 */
    if (v != NULL) {
        LCA(P, v, set, ancestor, visited);
        Union(set, u->data, v->data);
        ancestor[Find(set, u->data)] = u->data;
    }
    visited[u->data] = true;
    for (i = 0; i < P->size; i++) { /* 对P中的每个(u,v)中的v*/
        v_data = 0;
        if (P->nodes[i].u == u->data) {
            v_data = P->nodes[i].v;
        } else if (P->nodes[i].v == u->data) {
            v_data = P->nodes[i].u;
        }
        if (visited[v_data] == true) { /* 如果v也标记过了 */
            P->nodes[i].lca = ancestor[Find(set, v_data)]; /* 得到u 和v的LCA*/
        }
    }
}
/* 算法9-7 结束 */

void LeastCommonAncestor(BinaryTree tree, Query P) {
    Position root;
    Set set;
    Node ancestor[kMaxSize + 1]; /* 假设集合元素下标从1开始 */
    bool visited[kMaxSize + 1] = {false}; /* 假设集合元素下标从1开始 */

    root = tree;
    InitSet(set, kMaxSize);
    LCA(P, root, set, ancestor, visited);
}

int main(void) {
    BinaryTree tree;
    Query P;
    int m, i;

    tree = BuildTree(); /* 创建二叉树 */
    scanf("%d", &m);
    /* 创建查询集 */
    P = (Query)malloc(sizeof(struct QueryNode));
    P->size = m;
    P->nodes = (Pair)malloc(sizeof(struct PairNode) * m);
    for (i = 0; i < m;
            i++) { /* 读入待查询的结点对，并初始化其LCA为空 */
        scanf("%d %d", &P->nodes[i].u, &P->nodes[i].v);
        P->nodes[i].lca = NIL;
    }
    LeastCommonAncestor(tree, P); /* 求查询集P中所有结点对的LCA */
    for (i = 0; i < m; i++) {
        printf("LCA(%d, %d) = %d\n", P->nodes[i].u, P->nodes[i].v, P->nodes[i].lca);
    }
    return 0;
}

/* 创建树的操作 */
BinaryTree PreOrderDeSerialize(TElemSet preorder[], int n) {
    BinaryTree tree;
    TElemSet data;

    k++;
    tree = NULL; /* 初始化一个空树 */
    if (k < n) { /* k是线性表的有效序号 */
        data = preorder[k]; /* 读出线性表第k个元素 */
        if (data != NIL) {
            tree = (BinaryTree)malloc(sizeof(struct
                                             BinaryTreeNode));/* 新建二叉树结点 */
            tree->data = data; /* 代入数据 */
            tree->left = PreOrderDeSerialize(preorder, n); /* 重构左子树 */
            tree->right = PreOrderDeSerialize(preorder, n); /* 重构右子树 */
        }
    }
    return tree; /* 返回新建的二叉树或空树 */
}

BinaryTree BuildTree() {
    TElemSet *preorder;
    char s[kMaxStringSize + 1];
    int n, i;

    scanf("%d\n", &n);
    preorder = (TElemSet *)malloc(sizeof(TElemSet) * n);
    for (i = 0; i < n; i++) {
        scanf("%s ", s);
        if (s[0] == '#') {
            preorder[i] = NIL;
        } else {
            preorder[i] = atoi(s);
        }
    }
    k = -1;
    return PreOrderDeSerialize(preorder, n);
}
/* 创建树的操作 结束 */

/* 不相交集的操作 */
void InitSet(Set set, int n) {
    SElemSet x;

    for (x = 1; x <= n; x++) {
        set[x].parent = x;
        set[x].rank = 0;
    }
}

SetName Find(Set set, SElemSet x) {
    if (x != set[x].parent) {
        set[x].parent = Find(set, set[x].parent);
    }
    return set[x].parent;
}

void Union(Set set, SElemSet x, SElemSet y) {
    SetName i, j;

    i = Find(set, x);
    j = Find(set, y);
    if (i != j) {
        if (set[i].rank > set[j].rank) {
            set[j].parent = i;
        } else if (set[i].rank < set[j].rank) {
            set[i].parent = j;
        } else { /* set[i].rank == set[j].rank */
            set[i].parent = j;
            set[j].rank++;
        }
    }
}
/* 不相交集的操作 结束 */